\section{Recommender Systems}
\label{recommender}
The recommeder systems are developed to assist the user with the selection of items that they might be interested in. The abundance of variety of music available on the internet has made the music recommender system an essential tool for music listeners to find music of thier choice in large collections. According to \cite{schwartz} 'more is less' because when confronted with affluent choices, often consumers become dubious and find themselves in the state of ``analysis paralysis" which refers to indecisiveness caused by too many options. 

\subsection{Recommendation Problem}
A recommendation problem can be formalised as follows:
\paragraph{Formalisation of the Recommendation Problem}{The recommendation problem inherits prediction problem. When formalising the recommendation problem, one should first formalise the prediction problem \cite{OC10}.\\
Let, $U = {u_{1}, u_{2}, ... u_{m}}$ be the set of all users, and let $I = {i_{1}, i_{2}, ... i_{n}}$ be the set of all possible items that can be recommended. Each user $u_{i}$ has a list of items $I_{u_{i}}$ that the user is interested in. Where
 $I_{u_{i}}$ $\subseteq$ $I$ and $I_{u_{i}}$ can be empty i.e. $I_{u_{i}}$ = $\emptyset$. Then function $P_{u_{a}, i_{j}}$  is the predicted likeliness of item $i_{j}$ for the active user $u_{a}$, such as $i_{j}$ $\notin$ $I_{u_{a}}$.\\
Recommendation problem is reduced to bringing a list of N items, $I_{r}$ $\subset$ $I$, that the user will like the most (i.e. the ones with higher $P_{u_{a}, i_{j}}$ value). The recommended list should not contain items from user's interests, i.e. $I_{r}$ $\bigcap$ $I_{u_{i}}$ = $\emptyset$.\\
The space for $I$ items and $U$ users can be very large. In most recommender systems, the prediction function is usually represented by a rating which is stored as a triple $<u, i, r>$ where r is the value assigned explicitly or implicitly by the user $u$ to a particular item $i$. Usually, this value is a real number (e.g. from 0 to 1), a value in a discrete range (e.g. from 1 to 5), or a binary variable (e.g. like/dislike).}
The most popular families of recommendation strategies to solve the recommendation problem are as follows:

\subsection{Recommendation Algorithms}
The usefulness or utility of recommendation algorithm is dependent upon two phases. The first phase is the rating estimation phase in which known ratings as well as other information that might be available (e.g., content attributes of items or demographic attributes of users) to estimate ratings for items that the users have not yet consumed. Top-$N$ recommendations are generated, given all of the unknown item predictions for each user. In second phase, the system selects the most relevant items to the user, maximising the utility according to a certain ranking criterion.
%For clarity, we use , and  R*(u,i) for the system-estimated rating for item i that user u has not rated before. 
A formal definition of this would be: item $i_x$ is ranked ahead of item $i_y$, if $rank$($i_x$) \textless $rank$($i_y$), where rank: $I$ \rightarrow \bold{R} is a function representing ranking criterion. Most recommender systems rank the candidate items 
by their predicted rating value and recommend to each user the $N$ most highly predicted items. Only a limited number of recommendations are made due to constraints such as time at the user end. Therefore, $N$ is a relatively small positive integer representing items that users might be interested in. This ranking approach can formally be defined with ranking function: $rank_{Standard}(i)$=$R*(u,i)\textsuperscript{-1}$ where $R*(u,i)$ represents the system-estimated rating for item $i$ that user $u$ has not rated before and $R(u,i)$ to denote the actual rating that user $u$ gave to item $i$. This approach works well for recommendation accuracy but its performance in terms of recommendation diversity is poor \cite{}, which further emphasizes the need for different recommendation approaches for diversity improvement. Among a large number of recommendation techniques that have been developed over the past decade, collaborative filtering (CF) techniques represent most widely used and well-performing algorithms; we use two representative CF techniques for Phase 1 (i.e., rating estimation) in this paper: neighborhood-based CF and matrix factorization CF techniques. Neighborhood-based CF techniques.  The basic idea of neighborhood-based CF techniques is, given a target user, to find the user’s neighbors who share similar rating patterns, and then to use their ratings to predict the unknown ratings of the target user [1,9].  There are many variations of computational methods to identify a user’s neighbors (i.e.,  by computing the similarity between users) and aggregate the neighbors’ ratings for the user.  In our experiments, we use a popular cosine similarity measure for calculating similarity between users, and the final rating prediction for a specific item to a user is made as an adjusted weighted sum of the ratings of the user’s closest 50 neighbors on this item.  The neighborhood CF techniques can be user- or itembased, depending on whether the similarity is computed between users or items [33]; we use both variations in this paper. Matrix factorization CF techniques.  Matrix factorization CF techniques have recently gained popularity because of their effectiveness in the Netflix Prize competition in terms of predictive accuracy.  In contrast to heuristic-based techniques (such as the neighborhood-based CF techniques mentioned above), the matrix factorization CF techniques use the existing ratings to learn a model with k latent variables for users and items.  In other words, this technique models and estimates each user’s preferences for  k latent features as the user-factors vector and each item’s importance weights for the  k latent features as the item-factors vector [16,24].  Then, the predicted rating of item i for user u can be computed as an inner product of the user-factors vector for user u and the item-factors vector for item i.  Typically, the model-based techniques have  been shown to generate more accurate recommendations than heuristic-based techniques.  While a number of variations for the matrix factorization technique have been developed,  in this paper we use its basic version, as proposed by Funk [16].  

\subsubsection{Collaborative Filtering}
Collaborative Filtering is a widely used approach to solve the recommendation problem. The stored interaction (explicit or implicit) between the users of the system and the item set helps generate informed guesses for recommendations. This approximation is called collaborative filtering. The goal of this recommendation strategy is to return items with highest estimated ratings based on user's previous ratings for items \cite{1423975}. There are many disadvantages of using collaborative filtering such as cold start problem in which the user cannot be recommended many relevant items unless there are enough user profiles that contain sufficient information to relate to its related neighbours. There is also a new item problem, when there is no similar items to relate to a newly added item. Also, there exists sparsity problem which refers to a situation that transactional data are lacking or are insufficient. The problem to recommend items to indifferent users is also unresolved as the recommendations are not in accordance with the user's unique taste. It is easy to attack, if a group of members want to exploit the system. The solution proposed by \cite{Massa} deals with this issue by creating a trust relationship among users but it makes the system much more complicated and crowd wisdom is lost. The user's explicitly rated trust solution in FilmTrust \cite{1593032} seem to burden the user as the users usually have few trusted links. It seems sensible to work on a platform where this `trust' relationship has already been established between the users such as online social networks.

\subsubsection{Content-based Filtering}
The content-based filtering collects the information regarding the items and based on user preferences filters the results that the user is most likely to prefer.  It simply depends on item description rather than the user ratings.

\subsubsection{Context-based Filtering}
As the name signifies, the context-based filtering approach uses the contextual information to describe the items.

\subsubsection{Demographic Filtering}
The demographic filtering uses sterotyping. It filters the results based on stereotypes of users that like certain item. 

\subsubsection{Hybrid Filtering}
It is simply the combination of two or more recommendation startegies.

\subsubsection{utility-based}
\subsubsection{knowledge-based recommendations}
\subsection{Music Recommender System}
Music is inherently different than other types of media. The space of recommended items is extremely large as compared to other domains e.g. a typical online music store may offer 10 million titles to chose from. Interaction with music is also different than from other types of media. People enjoy listening to same music repeatedly which is not the case for other recommendable items such as books. Listeners vary their music preference based upon context and activities. A playlist for jogging is likely to be very different than a playlist created by the same user for relaxing. Listeners enjoy listening to sequences of songs often getting as much enjoyment from the song transitions as from the songs themselves. The uniqueness of music as recommendation domain present challenges not seen in other recommender domains. It is important to consider the special nature of music when building recommenders for music. Music Recommender System have become increasingly popular because people face difficulty to find their preferred music in the huge volume of music content and music-related information available these days. As a result of continued efforts, the quality of these systems has improved over time. However, more research in this area is required for coping with the dynamic world of web. 

In \cite{barrington2009smarter}, Barrington et al. compare the Genius recommender system with a recommender based solely on acoustic similarity, one based on artist similarity and random. They evaluate the three recommenders by doing playlist generation, a user is presented with a seed song which he rates on a 5 point scale, then he is presented with two playlists generated from either of the four recommenders and can remove songs that do not fit into the playlists in relation to the seed song and rate the playlists on a 5 point scale. The user is then asked to compare the two playlists by stating which is better. They experimented by both displaying and hiding the song name and artist. The results showed that seeing song and artist names has a significant effect on how a playlist is evaluated, indicating that recommender systems must be designed with applications in mind. They found that while Genius performs as well or better than the metadata and content-based systems on their test collection of popular music, it is unable to make recommendations from the long tail of new and undiscovered music.

In \cite{fields2009analysis} Fields et al. study the social network of musicians in MySpace. They use complex network theory and audio content analysis. They show that the artist network topology is related to music genres by clustering the network into communities based on the topology and tags. They show that the artist social graph and the acoustic dissimilarity matrix encode different relations. They conclude that these two relations are different sources for music recommenders.

In \cite{levy2009music}, Levy et al. describe a music retrieval system based on both social tags and audio content. Last.fm uses a combination of collaborative filtering and analysis of user-supplied tags for artists, albums and tracks. They analyse tag data from 5265 artists and show that one third have no tags for any of their tracks and another third have around 5 tags per tracks on average. This shows that tagging alone can not be used in a recommendation system, because of the cold start problem. They extract muswords for a track by identifying musical events within it, and then discretising timbral and rhythmic features for each region found. They combine tag data and muswords in a vector space and provide with an analysis of results using different parameters and various types of muswords.

In \cite{shardanand1995social}, Shardanand et al. introduce social information filtering and describe its implementation in a system called Ringo which started to make personalized music recommendations in July 1994. Social information filtering makes use of users' ratings to recommend items to each other. They propose and evaluate four algorithms, namely: the mean square differences algorithm, the pearson r algorithm, the constrained pearson r algorithm, and the artist-artist algorithm. According to their results, the constrained pearson r algorithm which takes into account the positive and negative correlations performed best in terms of number of correct recommendations performed. The artist-artist and mean square algorithms performed better in terms of quality of the recommendations but provided with less recommendations. They also report on qualitative aspects of Ringo, mainly stating that feedback from users changed over time going from saying that the recommendations were poor to saying that the recommendations were amazing as the system was getting bigger and therefore had more data to work from. 

Bogdanov et al.\cite{bogdanov10} present three different approaches to content-based recommendation based on musical dimensions such as genre and culture, moods and instruments, and rhythm and tempo extracted from audio features. They compare with recommendations from Last.fm in a user evaluation with 11 users. They expect the proposed approaches to be suitable for music discovery in the long tail which has a lack of contextual information, and incorrect or incomplete metadata.

In \cite{herrera10}, Herrera et al. analyse temporal patterns in users listening history. They use playcounts from last.fm to find patterns in the selection of artists or genres for certain moments of the day or for certain days of the week. They show that for certain users what to play at the "right" moment is predictable and could be used in recommendation systems.

Tomasik et al. \cite{tomasik2009using} show that using linear regression performs better than using sum or max when combining multiple data sources for music information retrieval. They combine data from text mining web documents to extract tags, content-based audio analysis to find acoustic features, and collaborative filtering. They run their experiment on a set of 10 thousand songs and use Pandora dictionary as ground-truth.

Aman et al.\cite{aman10} give a review of explanations, visualizations and interactive elements of user interfaces in music recommendation systems. They present a taxonomy of dimensions, namely : transparency, scrutability, effectiveness, persuasiveness, efficiency and trust. They measure recommendation aids across multiple systems according to these dimensions, Pandora and Amazon are the systems with the most recommendation aids.

\subsection{The long tail}

In \cite{levy10}, Levy et al. present their work in driving the Last.fm recommendations towards items from the long tail to remove the popularity bias. They show that there is no evidence that recommendations and radio cause a systematic bias towards more popular artists. They built a prototype recommender for long tail artists using item-based collaborative filtering with both scrobbles and tags. Their results suggest that the influence of such a recommender on users' general listening may be limited.

Lee\cite{lee10} et al. propose a collaborative filtering recommendation algorithm which removes the popularity bias. In fact recommendations from collaborative filtering often lead to "obvious" recommendations as most popular songs are the ones recommended. Their solution is to recommend songs coming from the long tail of "expert" users and novel to the user. They evaluate their algorithm by producing a page of recommendations for Last.fm users and contacted them by private message. After seeing the page, the user is asked to rate the list of recommendations on how much they liked them and how much novel they were. The survey was completed only by 11 users and show that the recommended items were mostly novel and relevant.

In \cite{gaffney2009making}, Gaffney et al. study the use of folksonomies for music discovery by users of social networking sites as a mean to discover items from the long tail. They examined in this project are MySpace, Lastfm, Pandora and Allmusic. They conducted interviews and questionnaires by contacting people outside concerts, directly on social networking sites and independent record companies. Although participants use social networking sites for music discovery, they found that people are still not using tags for discovery very much and that the ones who tag do it for personal future retrieval. 

\subsection{Recommender System and Social Web} 
The exponential growth of the social web continues to pose challenges and opportunities for recommender systems. The social web has turned information consumers into active contributors creating massive amounts of information. Finding relevant and interesting content at the right time and in the right context is challenging for existing recommender approaches. At the same time, social systems by their definition encourage interaction between users and both online content and other users, thus generating new sources of knowledge for recommender systems. Web 2.0 users explicitly provide personal information and implicitly express preferences through their interactions with others and the system (e.g. commenting, friending, rating, etc.). These various new sources of knowledge can be leveraged to improve recommendation techniques and develop new strategies which focus on social recommendation. The Social Web provides huge opportunities for recommender technology and in turn recommender technologies can play a part in fuelling the success of the Social Web phenomenon. The goal of this workshop, the third in the series, is to bring together researcher and practitioners to explore, discuss, and understand challenges and new opportunities for recommender systems and the Social Web.

\subsection{Social Music Recommender System}

The strengths of social media are appreciated widely. A quantitative survey and qualitative interviews conducted by Baker et al. revealed that social networking websites could generate a strong future for the distribution of music \cite{baker2009social}. The study conducted on MySpace shows that both artists and consumers react positively towards distribution and discovery of new music through social media platforms. Laplante in \cite{laplante2010role,laplante08} presents a prelimanary study of music discovery within a population of young adolescents. She reports on a social network analysis based on interviews of 6 participants. All participants affirmed that changes in their music taste reflects changes in their social network. The analysis revealed that music opinion leaders were perceived as  good communicators, who are highly invested in music, and who are willing to share the information with their friends, three of the participants identified themselves as opinion leaders. The exchange of music information strengthens relationships. Most participants recognize their parents or one of their parents to be very influencial in terms of music discovery. Also, \cite{tepper2009pathways} found that social networks are the main source for music discovery for college students. They conclude that technology will be used to reinforce existing social patterns and relationships, rather than transform them. Therefore, while designing new software systems social music recommendations should be taken into account.\\
Web Music Communities (WMC) like Last.fm\footnote{\url{http://www.last.fm}}, Pandora\footnote{\url{http://www.pandora.com}} and Ping\footnote{\url{http://www.apple.com/itunes/ping}} are playing vital role in helping music listeners to build relations with similar music-listeners, get recommendations based on their current music collections and much more. All the music recommendation systems make use of the user provided information in order to generate relevant recommendations upon the information available. If music recommender systems take into account the social aspect of the music then it is possible to tailor music listener's socially influenced music taste. A successful attempt to model the user intentions and its extraction may further be applied in other relevant areas.\\
The existing recommendation techniques such as content-based, collaborative filtering or hybrid techniques focus on users explicit contact behaviors but ignore the implicit relationship among users in the network. It is important to realise the significance of relationships in social networks. Due to the higher expectation of users, online dating networks are trying to adopt recommender systems. A social matching system that uses past relations and user similarities in finding potential matches. Empirical analysis on the dataset collected from an online dating network shows that the recommendation success rate has increased to 31\% as compared to the baseline success rate of 19\% \cite{ICDMW} when the social aspect is taken into consideration. Similar improvements might be acheived when user's music collections are integrated into social platforms for example, Google provides music storage solution for music fans, unlike Facebook that does not provide its user with the feature of sharing music collection\footnote{\url{http://evolver.fm/2011/07/06/5-ways-google-could-steal-music-fans-from-facebook/}}. If music collection are made visible and searchable on Social Networks like Google+\footnote{\url{https://plus.google.com/}} and Facebook, it could be used as a way to introduce people to each other, work on creating DMCA-compliant streams that would allow people to listen to each other’s taste, and use taste-combining algorithms to create stations out of multiple accounts created on services like Music Beta by Google\footnote{\url{http://music.google.com/}}.\\
Comparison of Apple's Genius music recommender system with recommender systems based on acoustic similarity, artist similarity and random showed that Genius performs similar or better than the metadata and content-based recommender systems on user's test collection of popular music. But the drawback of such systems are that it is unable to make recommendations from the long tail of new and undiscovered music \cite{barrington2009smarter}. This study also reveled that seeing song and artist names has a significant effect on how a playlist is evaluated.

%Although, there is a strong bias toward audio-based approaches as most MIR researchers have strengths in signal processing in the music information retrieval community such as MIREX and MIR \cite{MIR}. The importance of music social aspects are also considered important by many musicologists and scientists \cite{Laplante08}, \cite{}

\section{Relevance}
\subsection{Novelty, Fimiliarity, Serendipity and Relevance}

As already discussed, recommendation is a complex problem due to context blindness. In order to integrate different 

In \cite{celma08} Novelty is defined by the equation, the unknown items in the list of top-N recommended items, \mathcal{L}_N
	\begin{equation}
		Novelty(u) = \frac{\sum_{i\in\mathcal{L}_N} (1-Knows(u,i))}{N}
	\end{equation}
where, $Knows(u,i)$ is a binary function that returns 1 if user $u$ already knows item $i$, and 0 otherwise. Likewise, user's familiarity with the list of recommended items can be defined as $Familiar$(u)=1-$Novelty$(u).

Ideally, user should be familiar with the some of the recommended items, to improve confidence and trust in system. Also, some items should be unknown to the user (discovering hidden items in the catalog). Explanation of recommendations can increase the level of confidence of users in the system. 

I strongly believe that this cannot be true representation of novelty in terms of software detected non-listened track assumed to be `unknown'. Since, the track/song/album might already be known to the user in other settings in life such as party, restaurant, etc. Therefore, a software determined known/unknown track can only be an estimate not absolute measure. Hence, if we take the `knows' in fuzzy logic terms that would represent an estimation better.


